import java.util.Arrays;

/**
 * 64. Minimum Path Sum 最小路径和
 * https://leetcode-cn.com/problems/minimum-path-sum/
 */
class MinimumPathSum {
    /**
     * 方法：动态规划，从左上到右下计算最小路径和
     * 
     * Args:
     *   grid: int[][] - 给定的网格，每个位置包含非负整数
     * 
     * Returns:
     *   int: 从左上角到右下角的最小路径和
     * 
     * Time: O(m*n) - m和n分别为网格的行数和列数，需要遍历整个网格
     * 
     * Space: O(m*n) - 使用二维dp数组存储中间结果
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] f = new int[m+1][n+1];
        Arrays.fill(f[0], Integer.MAX_VALUE);
        f[0][1] = 0;
        for(int i = 0; i< m; i++){
            f[i+1][0] = Integer.MAX_VALUE;
            for(int j = 0; j<n; j++){
                f[i+1][j+1] = Math.min(f[i][j+1], f[i+1][j]) + grid[i][j];
            }
        }
        return f[m][n];
    }

    /**
     * 方法：动态规划，使用一维数组优化空间复杂度
     * 
     * Args:
     *   grid: int[][] - 给定的网格，每个位置包含非负整数
     * 
     * Returns:
     *   int: 从左上角到右下角的最小路径和
     * 
     * Time: O(m*n) - m和n分别为网格的行数和列数，需要遍历整个网格
     * 
     * Space: O(n) - 只使用一维数组存储中间结果，n为网格的列数
     */
    public int minPathSum1(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] f = grid[0];
        for(int j = 1; j < n; j++){
            f[j] += f[j-1];
        }
        for(int i = 1; i < m; i++){
            f[0] += grid[i][0];
            for(int j = 1; j < n; j++){
                f[j] = Math.min(f[j-1], f[j]) + grid[i][j];
            }
        }
        return f[n-1];
    }

    /**
     * 方法：动态规划，直接在原数组上修改，不使用额外空间
     * 
     * Args:
     *   grid: int[][] - 给定的网格，每个位置包含非负整数
     * 
     * Returns:
     *   int: 从左上角到右下角的最小路径和
     * 
     * Time: O(m*n) - m和n分别为网格的行数和列数，需要遍历整个网格
     * 
     * Space: O(1) - 直接在原数组上修改，不使用额外空间
     */
    public int minPathSum2(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 处理第一行，从左到右
        for(int j = 1; j < n; j++){
            grid[0][j] += grid[0][j-1];
        }
        // 处理第一列。 从上到下
        for(int i = 1; i < m; i++){
            grid[i][0] += grid[i-1][0];
        }
        // 处理其他位置：可以从上或从左移动过来
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
}